package arrAndstr;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/*
    103. 二叉树的锯齿形层序遍历
 */
public class T103 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        boolean flag = true;    // true --> 左；false --> 右

        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            // 必须顺序存储，但是可能逆序读取
            int num = queue.size();

            // 存储
            List<TreeNode> tempList = new ArrayList<>();
            for (int i = 0; i < num; i++) {
                TreeNode node = queue.poll();
                tempList.add(node);

                if (node.left != null)  queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }

            // 读取
            if (flag) { // 从左往右
                for (TreeNode node : tempList) {
                    list.add(node.val);
                }
            } else {
                for (int i = num-1; i >= 0 ; i--) {
                    list.add(tempList.get(i).val);
                }
            }
            flag = !flag;

            result.add(list);
        }

        return result;
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(3);
        node.left = new TreeNode(9);
        node.right = new TreeNode(20);
        node.right.left = new TreeNode(15);
        node.right.right = new TreeNode(7);
        System.out.println(zigzagLevelOrder(node));
    }

}
